/*
5.25
time:20201120 12:00 PM
key:1.
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
class Tree
{
public:
	int data;
	Tree* lchild;
	Tree* rchild;
	bool left_flag = false;   //左指针域类型  false：指向子节点、true：前驱或后继线索
	bool right_flag = false;  //右指针域类型  false：指向子节点、true：前驱或后继线索

	Tree()
	{
		data = -1;
		lchild = NULL;
		rchild = NULL;
	}
};
void write(Tree* node)
{
	if (node != NULL)
	{
		int a;
		cin >> a;
		if (a != 0)
		{
			node->data = a;
			node->lchild = new Tree;
			node->rchild = new Tree;
		}
		write(node->lchild);
		write(node->rchild);
	}
}
//中序遍历输出树()
void PerOrder(Tree* node)
{
	if (node != NULL)

	{
		PerOrder(node->lchild);
		cout << node->data << " ";
		
		PerOrder(node->rchild);
		
	}
}
//先序遍历输出树(-1空节点改为NULL)
void change(Tree* node)
{
	if (node != NULL)

	{
		if (node->lchild->data == -1)
		{
			node->lchild = NULL;
		}
		if (node->rchild->data == -1)
		{
			node->rchild = NULL;
		}
		change(node->lchild);
		change(node->rchild);

	}
}
/*线索化中序遍历*/
void check(Tree* root)
{
	while (root)
	{
		while (root->left_flag != true)
			root = root->lchild;
		cout << root->data << " ";
		while (root->right_flag != false)
		{
			root = root->rchild;
			cout << root->data << " ";
		}
		root = root->rchild;
	}
	cout << endl;
}
/*线索化中序遍历改动s节点*/
void change2(Tree* root, Tree* l, int s)
{
	while (root)
	{
		while (root->left_flag != true)
		{
			root = root->lchild;
		}
		if (root->data == s) 
		{
			root->lchild = l;
			break;
		}
		cout << root->data << " ";
		while (root->right_flag != false)
		{
			root = root->rchild;
			cout << root->data << " ";
			if (root->data == s)
			{
				root->lchild = l;
				break;
			}
		}
		root = root->rchild;
	}
	cout << endl;
}
/*中序遍历的构建*/
void inCreate(Tree* root, Tree*& prev)
{
	if (root)
	{
		inCreate(root->lchild, prev);
		if (root->lchild == NULL)
		{
			root->left_flag =true;
			root->lchild = prev;
		}
		if (prev && prev->rchild == NULL )
		{
			prev->right_flag = true;
			prev->rchild = root;
		}
		prev = root;
		inCreate(root->rchild, prev);
	}
}
/*无空指针的中序遍历的构建*/
void inCreate2(Tree* root, Tree*& prev)
{
	if (root)
	{
		if (root->left_flag == false)//特别注意，现在已经没有空指针了，不能无条件的进去root->lchild，因为有root->lchild=prev会死循环.
		{
			inCreate2(root->lchild, prev);
		}
		if (root->lchild == NULL||root->left_flag==true )
		{
			root->left_flag = true;
			root->lchild = prev;
		}
		if ((prev && prev->rchild == NULL) || (prev->right_flag == true))
		{
			prev->right_flag = true;
			prev->rchild = root;
		}
		prev = root;
		if (root->right_flag == false) //特别注意，现在已经没有空指针了，不能无条件的进去root->rchild，因为有root->rchild=prev会死循环.
		{
			inCreate2(root->rchild, prev);
		}
	}
}

int main()
{
	Tree* head = new Tree;
	stack<Tree*>rchild_stack;
	stack<Tree*>child_stack;

	//使用一下输入
	//1 2 3 0 0 4 0 5 0 0 6 0 7 0 8 0 0
	write(head);
	cout << "先序遍历输出树(-1是空节点)" << endl;
	PerOrder(head);
	cout << "\n先序遍历改造树(-1空节点改为NULL)" << endl;
	change(head);
	cout << "\n线索化二叉树" << endl;
	Tree* headhead = new Tree;
	headhead->right_flag = true;
	headhead->left_flag = true;
	headhead->data = 0;
	headhead->rchild = head;
	inCreate(head,headhead);
	cout << "\n中序检验" << endl;
	check(head);
	cout << "\ns节点的数据输入" << endl;
	int s;
	cin >> s;
	cout << "\n新节点l的数据值" << endl;
	int ll;
	cin >> ll;
	cout << "\n新节点l插入s左节点" << endl;
	Tree* l = new Tree;
	l->data = ll;
	change2(head, l, s);
	cout << "\n线索化二叉树" << endl;
	Tree* headhead1 = new Tree;
	
	headhead1->left_flag = true;
	headhead1->data = 0;
	headhead1->rchild = head;
	inCreate2(head, headhead1);
	cout << "\n中序检验" << endl;
	check(head);



}




